package org.labuladong.动态规划算法.二维DP;

/**
 * @Auther: qingle
 * @Date: 2024/10/26-22:43
 * @Description:
 *
 * 给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最⼩步数，每步可以删除任意⼀个字
 * 符串中的⼀个字符。
 * 示例：
 * 输⼊："sea", "eat"
 * 输出：2
 * 解释：第⼀步将 "sea" 变为 "ea"，第⼆步将 "eat" 变为 "ea"
 *
 * 最⻓公共⼦序列的⻓度
 *最长公共子序列（Longest Common Subsequence, LCS）是动态规划问题的另一个经典例子。这个问题与最长公共子串（Substring）不同，子序列不需要在原始序列中连续出现。
 *
 * 以下是一个Java实现，用于计算两个字符串的最长公共子序列的长度：
 * @version: 1.0
 */
public class LC_583_两个字符串的删除操作 {

	public static int minDistance(String word1, String word2)
	{
		int m = word1.length();
		int n = word2.length();
		return m + n - 2 * lcs(word1, word2);
	}
	public static int lcs(String word1, String word2)
	{
		int m = word1.length();
		int n = word2.length();

		char[] X = word1.toCharArray();
		char[] Y = word2.toCharArray();
		// 创建二维数组存储中间结果
		int[][] dp = new int[m + 1][n + 1];

		// 构建dp数组
		for (int i = 0; i <= m; i++) {
			for (int j = 0; j <= n; j++) {
				if (i == 0 || j == 0) {
					dp[i][j] = 0;
				} else if (X[i - 1] == Y[j - 1]) {
					dp[i][j] = dp[i - 1][j - 1] + 1;
				} else {
					dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
				}
			}
		}
		return dp[m][n];
	}





	public static void main(String[] args)
	{
		System.out.println(minDistance("sea", "eat"));
	}

}
